5621. Find a multiple

 

Given n positive integers, each is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers (1 ≤ few ≤ n) so that the sum of chosen numbers is multiple for n (i.e. n * k = (sum of chosen numbers) for some integer k).

 

Input. First line contains number n (n ≤ 10000). Each of next n lines contains one number from the given set.

 

Output. If the answer can not be found, print 0. Otherwise print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order.

If there are more than one set of numbers with required properties, print any of them.

 

Sample input

Sample output

5

1

2

3

4

1

2

2

3

 

 

SOLUTION

mathematics

 

Algorithm analysis

Let d1, d2, …, dn be the input numbers. Consider all partial sums si = d1 + … + di. Since we have exactly n partial sums, then among all values of si mod n there must be either two identical or such i that si mod n = 0.

If sa-1 mod n = sb mod n for a – 1 < b, then da + … + db is divisible by n. Set of numbers da, da + 1, …, db will be the answer. If there is such i that si mod n = 0, then the answer is d1, d2, …, di.

 

Example

Consider the sample given. Compute all partial sums:

 

 

There are several required sets. For example:

·        since s1 = s3, then d2 + d3 = 5 is divisible by 5.

·        since s1 = s5, then d2 + d3 + d4 + d5 = 10 is divisible by 5.

·        since s3 = s5, then d4 + d5 = 5 is divisible by 5.

·        since s4 = 0, then d1 + d2 + d3 + d4 = 10 is divisible by 5.

 

Algorithm realization

Store the input numbers in the array d. We will use the array r to mark partial sums: if s = d1 + … + di, then we put r[s] = i.

 

#define MAX 10100

int d[MAX], r[MAX];

 

A set of numbers, the sum of which is divisible by n, will be d[a], d[a + 1], …, d[b]. We print their number b – a + 1, as well as the numbers themselves, one in one line.

 

void print(int a, int b)

{

  printf("%d\n",b - a + 1);

  for(int i = a; i <= b; i++)

    printf("%d\n",d[i]);

}

 

The main part of the program.

 

memset(r,-1,sizeof(r)); r[0] = 0;

scanf("%d",&n);

for(sum = 0, i = 1; i <= n; i++)

{

  scanf("%d",&d[i]);

  sum = (sum + d[i]) % n;

 

If a partial sum equal to sum is encountered for the second time, then we print the set of required numbers dr[sum] + 1, …, di.

 

  if (r[sum] != -1)

  {

    print(r[sum]+1,i);

    break;

  }

  else r[sum] = i;

}